//1.计数排序，遍历两次
class Solution {
public:
    void sortColors(vector<int>& nums) {
        int n = nums.size();
        int zeroCnt = 0, oneCnt = 0;
        
        // 统计0和1的数量
        for (int i = 0; i < n; i++) {
            if (nums[i] == 0) zeroCnt++;
            else if (nums[i] == 1) oneCnt++;
        }
        
        // 重构数组
        for (int i = 0; i < zeroCnt; i++) {
            nums[i] = 0;
        }
        for (int i = zeroCnt; i < zeroCnt + oneCnt; i++) {
            nums[i] = 1;
        }
        for (int i = zeroCnt + oneCnt; i < n; i++) {
            nums[i] = 2;
        }
    }
};

//2.单指针
class Solution {
public:
    void sortColors(vector<int>& nums) {
        int n = nums.size();
        int ptr = 0;
        for (int i = 0; i < n; ++i) {
            if (nums[i] == 0) {
                swap(nums[i], nums[ptr]);
                ++ptr;
            }
        }
        for (int i = ptr; i < n; ++i) {
            if (nums[i] == 1) {
                swap(nums[i], nums[ptr]);
                ++ptr;
            }
        }
    }
};
//3.三指针
class Solution {
public:
    void partition(vector<int>& nums, int L, int R)
    {
        int index = L;      // 当前遍历的元素索引
        int less = L - 1;   // 小于1区域的右边界（初始不存在）
        int more = R + 1;   // 大于1区域的左边界（初始不存在）
        /*
        小于 1 的区域：元素值为 0，范围是[L, less]。
        等于 1 的区域：元素值为 1，范围是(less, index)。
        大于 1 的区域：元素值为 2，范围是[more, R]。
        未处理区域：范围是[index, more)。
        */
        // 当index未到达大于1区域的左边界时继续循环
        while (index < more)
        {
            if (nums[index] == 1)
            {
                // 当前元素等于1，直接扩展等于1的区域
                index++;
            }
            else if (nums[index] < 1)
            {
                // 当前元素小于1，将其交换到小于区域，并扩展小于区域
                swap(nums[index++], nums[++less]);
            }
            else
            {
                // 当前元素大于1，将其交换到大于区域，并扩展大于区域
                // 注意：这里index不增加，因为从more区域交换过来的元素还未检查
                swap(nums[index], nums[--more]);
            }
        }
    }
//   当与more区域交换时，新元素可能是 0 或 1，需重新检查，因此index不移动。
//   当与less区域交换时，由于less区域右侧的元素已确认是 1，交换后index可直接右移。
    void sortColors(vector<int>& nums) 
    {
        partition(nums, 0, nums.size() - 1);
    }
};



